ON UNRELIABILITY OF FUNCTIONAL ELEMENTS CIRCUITS WITH TWO TYPES OF FAULTS

Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia), dm@pnzgu.ru
Barsukova Oksana Yurievna, Postgraduate student, Penza State University (40 Krasnaya street, Penza, Russia), dm@pnzgu.ru

519.718

Background. In modern mathematics and engineering the theory of circuits synthesis consisting of unreliable functional elements is of much interest. Until now (as far as we know) the problems of the Boolean functions realization using robust circuits have been solved on the assumption that the functional elements are exposed to only one type of faults (inverse faults at the output or constant faults at the input). This paper is among the first to consider in detail the problem of robust circuits synthesis with two types of faults. It is assumed that the functional elements are assigned to the Sheffer stroke function (disjunction) and the functional elements get faulty independently of each other. The first type of faults is noted for the fact that there is a certain probability of a value opposite to conjunction of the input values at the out-put (i.e. inverse faults at the output). There a certain probability of the second type faults at any input and the faults are characterized by the uncertainty at the output. It should be also noted that on every stage the functional element is exposed to only one of these two faults. The purpose of this paper is to study the possibility of constructing robust circuits, to find a method of reliable circuit synthesis, to obtain non-trivial upper and lower bounds of the circuits reliability estimation.
Results. The method of improving reliability of circuits with the described faults has been proposed, and it has been proved that, firstly, any Boolean function can be realized by a circuit, unreliability of which is asymptotically three times no more than unreliability of the functional element, and secondly, this estimation of reliability for almost all functions (the set is denoted by K) cannot be improved, i.e. unreliability of any circuit realizing the function of the K set is asymptotically three times less than unreli-ability of the functional element. The functions of the K set are explicitly described.
Conclusions. It is possible to construct reliable circuits with the described faults of elements. Moreover, the method of improving reliability of circuits and obtaining upper and lower bounds for circuit reliability has been found. These estimates were asymptotically equal to the functions of the K set, i.e. for almost all Boolean functions.

functional elements, unreliable functional elements, probability of faults, unreliability of a circuit.

1. Lupanov O. B. Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem [Asymptotical estimate of control system complexity]. Moscow: Izd-vo Mosk. un-ta, 1984, 138 p.
2. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathematics]. Moscow: Nauka, 1986, 384 p.
3. Alekhina M. A. Sintez asimptoticheskikh optimal'nykh po nadezhnosti skhem [Synthesis of of asymptotical safety-optimal circuits]. Penza: Inf.-izd. center PenzGU, 2006, 156 p.